package book;

public class BoardCoverSolution {
    int k;
    char[][] board;
    char tile = 'a';

    // 初始化棋盘的大小，以及特殊方格的位置
    public BoardCoverSolution(int k, int dr, int dc) {
        this.k = k;
        board = new char[1 << k][1 << k];
        board[dr][dc] = '-';
    }

    // 递归求解棋盘覆盖问题
    public void chessBoard(int r, int c, int size, int dr, int dc) {
        if (size < 2)
            return;
        char t = tile++; // 当前骨牌用字母变量 t 表示
        int s = size / 2; // 分割棋盘

        // 处理左上角子棋盘
        if (dr < r + s && dc < c + s)
            chessBoard(r, c, s, dr, dc); // 特殊方格在该子棋盘
        else {
            // 将子棋盘右下角用骨牌 t 所覆盖
            board[r + s - 1][c + s - 1] = t;
            // 递归求解左上角子棋盘的覆盖问题
            chessBoard(r, c, s, r + s - 1, c + s - 1);
        }

        // 处理右上角子棋盘
        if (dr < r + s && dc >= c + s)
            chessBoard(r, c + s, s, dr, dc); // 特殊方格在该子棋盘
        else {
            // 将子棋盘左下角用骨牌 t 所覆盖
            board[r + s - 1][c + s] = t;
            // 递归求解右上角子棋盘的覆盖问题
            chessBoard(r, c + s, s, r + s - 1, c + s);
        }

        // 处理左下角子棋盘
        if (dr >= r + s && dc < c + s)
            chessBoard(r + s, c, s, dr, dc); // 特殊方格在该子棋盘
        else {
            // 将子棋盘右上角用骨牌 t 所覆盖
            board[r + s][c + s - 1] = t;
            // 递归求解左下角子棋盘的覆盖问题
            chessBoard(r + s, c, s, r + s, c + s - 1);
        }

        // 处理右下角子棋盘
        if (dr >= r + s && dc >= c + s)
            chessBoard(r + s, c + s, s, dr, dc); // 特殊方格在该子棋盘
        else {
            // 将子棋盘右下角用骨牌 t 所覆盖
            board[r + s][c + s] = t;
            // 递归求解左上角子棋盘的覆盖问题
            chessBoard(r + s, c + s, s, r + s, c + s);
        }
    }

    // 结果输出显示
    public void printBoard() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++)
                System.out.print(" " + board[i][j]);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        BoardCoverSolution sln = new BoardCoverSolution(2, 0, 1);
        sln.chessBoard(0, 0, 4, 0, 1);
        sln.printBoard();
    }
}
